#include <algorithm>
#include <cstdint>
#include <iostream>
#include <istream>
#include <queue>
#include <vector>
using ll = int64_t;
#define sl static inline
const ll maxn = 100000+7, maxm=500000+7,inf=1e9+7;
ll n,m,p[maxn],maxp[maxn],minp[maxn],ans=-inf;
std::vector<std::vector<ll>> edg,redg;
int main(){
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin>>n>>m;
    edg.resize(n+1);
    redg=edg;
    std::fill(maxp+1,maxp+1+n,-inf);
    std::fill(minp+1,minp+1+n,inf);
    for(ll i=1;i<=n;i++){
        std::cin>>p[i];
    }
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        std::cin>>x>>y>>z;
        if(z==1){
            edg[x].emplace_back(y);
            redg[y].emplace_back(x);
        }else{
            edg[x].emplace_back(y);
            edg[y].emplace_back(x);
            redg[x].emplace_back(y);
            redg[y].emplace_back(x);
        }
    }
    
    std::queue<ll> q;
    q.emplace(n);
    maxp[n]=p[n];
    while(q.size()){
        ll u=q.front();
        q.pop();
        for(ll v:redg[u]){
            if(maxp[u]<=maxp[v]){
                continue;
            }
            maxp[v]=std::max(p[v],maxp[u]);
            q.emplace(v);
        }
    }
    minp[1]=p[1];
    q.emplace(1);
    while(q.size()){
        ll u=q.front();
        q.pop();
        ans=std::max(maxp[u]-minp[u],ans);
        for(ll v:edg[u]){
            if(minp[u]>=minp[v]){
                continue;
            }
            minp[v]=std::min(p[v],minp[u]);
            q.emplace(v);
        }
    }
    std::cout<<ans<<"\n";
}
